The paper proposes a simple algorithm for L_p regression problems and justifies its efficiency both theoretically and empirically. Major concerns: 1) Related work: The comparison with related works is not sufficient. In Section, it only compares with the polynomial dependence. What are the advantages of the proposed one? Furthermore, the lack of sufficient baselines (at least Bubeck et al. [BCLL19] or Adil et al. [AKPS19]) in the numerical experiments weakens the superior of the proposed algorithm.

This paper proposes a modified IRLS algorithm and presents empirical experiments and theoretical analysis. The reviewers viewed the contribution as a combination of existing methods, and the combination is novel. Most reviewers thought the paper was well-written. The ability of the authors to compare to existing methods is limited because of the complexity of other methods and lack of public implementations. The reviewers' scores place this paper above the bar for acceptance.

Linear regression in Lp-norm is a canonical optimization problem that arises in several applications, including sparse recovery, semi-supervised learning, and signal processing. Generic convex optimization algorithms for solving Lp-regression are slow in practice. Iteratively Reweighted Least Squares (IRLS) is an easy to implement family of algorithms for solving these problems that has been studied for over 50 years. However, these algorithms often diverge for p 3, and since the work of Osborne (1985), it has been an open problem whether there is an IRLS algorithm that converges for p 3. We propose p-IRLS, the first IRLS algorithm that provably converges geometrically for any p \in [2,\infty). Our algorithm is simple to implement and is guaranteed to find a high accuracy solution in a sub-linear number of iterations.

Linear regression in L_p-norm is a canonical optimization problem that arises in several applications, including sparse recovery, semi-supervised learning, and signal processing. Generic convex optimization algorithms for solving L_p-regression are slow in practice. Iteratively Reweighted Least Squares (IRLS) is an easy to implement family of algorithms for solving these problems that has been studied for over 50 years. However, these algorithms often diverge for p 3, and since the work of Osborne (1985), it has been an open problem whether there is an IRLS algorithm that converges for p 3. We propose p-IRLS, the first IRLS algorithm that provably converges geometrically for any p \in [2,\infty). Our algorithm is simple to implement and is guaranteed to find a high accuracy solution in a sub-linear number of iterations. Our experiments demonstrate that it performs even better than our theoretical bounds, beats the standard Matlab/CVX implementation for solving these problems by 10–50x, and is the fastest among available implementations in the high-accuracy regime.